Memory management issues are central to program performance, because memory is a scarce resource for processors. Therefore, it is incumbent for computer processes to use memory resources most efficiently in order for a program to scale well. It is also relatively expensive in terms of operating processor resources to allocate memory during a programming operation. Consequently, most computer programs spend a considerable amount of operation time in allocating and freeing memory.
Memory management generally involves manipulating a data structure known as the “heap.” For practical purposes, a heap includes a large block or segment of a processor that the computer makes available to the program. A newly started program has a large clean and coherent heap. However, as a program runs for an extended period of time, the heap degrades. The large clean and coherent heap becomes splintered into many smaller memory segments. As a result, complicated data structures are necessary to keep track of all of the smaller segments. As further degradation occurs, the operating resource cost of allocating and freeing a block of memory necessary increases.
To prevent splintering memory into ever-smaller segments, some memory manager programs allocate memory on selected block sizes. For example, a memory manager program may return 128 bytes in response to any request for 100 bytes. When this memory is released, the memory manager can use that buffer for any future request no greater than 128 bytes. This is effective at reducing memory fragmentation for a general-purpose memory allocator. Unfortunately, use of a buffer introduces significant overhead when allocating many blocks of a specific size.
Another problem for memory manager programs deals with locality of the data. Since a memory manager program typically has no knowledge about how to use the memory blocks, there can be no guarantee that similar data blocks are located near each other in the processor memory. When the various memory blocks are accessed, the operating system has to retrieve the correct “page” of memory. Such memory may be paged out to a disk, in RAM, in the cache or already present in the CPU itself. As computer operating speeds continue to increase, the difference in speed between accessing these various types of memory continues to increase. The operating system may attempt to access as the fastest available memory the most recently used memory and the memory just past that currently in use. This requires the use of a read-ahead that assumes that such memory will be next accessed. Since a memory manager program cannot guarantee that related blocks are kept near each other, applications that allocate and release many small blocks tend to have very poor locality characteristics. The result is yet poorer performance.
Memory management, therefore, represents an important area of computer process architecture. Accordingly, many strategies have emerged to maximize the efficiency of memory allocators that support memory management requirements. One such technique is generally referred to as a “memory pool.” In the memory pool approach, a large block of memory is allocated and partitioned into equal sized pieces. These equal sized pieces are held in some kind of list, usually a linked list. Whenever the programming computer process needs a block of memory of that size, the process will access a block off this list, instead of accessing the general memory manager.
Several advantages associate with the use of a memory pool. For instance, the individual blocks in the pool require no memory overhead to keep track of them. Consequently, using a memory pool can be quite efficient. Allocations and memory frees are quite efficient, because simply accessing the memory pool requires no searching. Only the top of the memory stack is manipulated. And, quite importantly, memory pool usage reduces the demands on the general memory manager, which may manage the rest of the computer's memory more efficiently.
There are, however, limitations associated with the use of a memory pool. First of all, with the memory pool, the client program must manage the memory allocation and release. Another limitation relates to the requirement that the memory in question must generally be allocated for the full operational period of the computer program. Although individual allocations and frees are quite efficient, when compared to the general memory manager, handling large numbers of individual allocations are still expensive. This follows from the requirement that each object must be added to and removed from lists individually.
Another approach to efficient memory management calls for allocating memory off of the “stack.” For the most part, this corresponds to a program's “local variables.” Stack allocations are generally very fast, since they require only a single subtraction. They also provide the additional benefit of not degrading the stack at all. This benefit distinguishes from heap allocations, which progressively degrade the heap over time, as described above.
There are, however, two significant limitations associated with the use of stack memory. The first limitation exists when the total amount of memory available is quite restricted when compared with the total heap memory. The second limitation is that stack memory becomes inaccessible when the function in which it was allocated “falls out of scope. This is true, even though stack memory may be very useful for problems that are clearly bounded in time.